#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#pragma warning(disable : 4996)

// �����ַ���������СдӢ����ĸ�������֣������֡�-��.
int trieParser(char ch)
{
    printf("%s called\n", __FUNCTION__);
    if (ch >= 'A' && ch <= 'Z')
        ch = 'a' + ch - 'A';
    if (ch >= 'a' && ch <= 'z')
        return ch - 'a';
    if (ch >= '0' && ch <= '9')
        return ch - '0' + 26;
    if (ch == '-')
        return 36;
    if (ch == '.')
        return 37;
    return -1;
}

// Trie�����ݽṹ
typedef struct Trie
{
    struct Trie *children[38];
    short end;
} Trie;

// ����Trie��������ָ��
Trie *trieCreate()
{
    Trie *ret = (Trie *)malloc(sizeof(Trie));
    memset(ret->children, 0, sizeof(ret->children));
    ret->end = -1;
    printf("%s called\n", __FUNCTION__);
    return ret;
}

// �������ַ���
void trieInsert(Trie *obj, char *word, short num)
{
    int n = strlen(word);
    for (int i = 0; i < n; i++)
    {
        if (word[i] == '*')
            for (int j = 0; j < 38; j++)
                trieInsert(obj, word + i, num);
        else
        {
            int ch = trieParser(word[i]);
            if (ch == -1)
            {
                printf("ERROR");
                return;
            }
            if (obj->children[ch] == NULL)
            {
                obj->children[ch] = trieCreate();
            }
            obj = obj->children[ch];
        }
    }
    obj->end = num;
    printf("%s called\n", __FUNCTION__);
}

// ���������ַ����Ƿ����
// �������ڣ�����-1
// �����ڣ�����endֵ
short trieSearch(Trie *obj, char *word)
{
    printf("%s called\n", __FUNCTION__);
    int n = strlen(word);
    printf("n = %d\n", n);
    printf("word = %s\n", word);
    for (int i = 0; i < n; i++)
    {
        int ch = trieParser(word[i]);
        printf("ch = %c\n", ch);
        if (ch == -1)
        {
            printf("ERROR");
            return -1;
        }
        if (obj->children[ch] == NULL)
        {
            return -1;
        }
        obj = obj->children[ch];
    }
    printf("%s called\n", __FUNCTION__);
    return obj->end;
}

// �����ַ���ǰ׺�Ƿ����
bool trieStartWith(Trie *obj, char *prefix)
{
    int n = strlen(prefix);
    for (int i = 0; i < n; i++)
    {
        int ch = trieParser(prefix[i]);
        if (obj->children[ch] == NULL)
        {
            return false;
        }
        obj = obj->children[ch];
    }
    return true;
}

// �ͷ�Trie��
void trieFree(Trie *obj)
{
    for (int i = 0; i < 38; i++)
    {
        if (obj->children[i])
        {
            trieFree(obj->children[i]);
        }
    }
    free(obj);
    printf("%s called\n", __FUNCTION__);
}
